Hilbert Projection Theorem

Let HH be a Hilbert space ( inner product space that is complete with respect to the norm induced by the inner product) and MM be a finite dimensioal subspace of HH. Then for any xHx \in H, there exists a unique yMy \in M such that

minmMxm\min_{m \in M} \|x-m\|

has a unique solution yy. In other words "we can find a unique point in MM that is closest to xx". If mm^* is the closest point to xx in MM, then xmMx-m^* \perp M.

Proof: See lecture notes.

Remark: The proof stated that m=x1m^* = x_1 is the closest point to MM. It can also be interpreted as the best approximation of xx choosen from the vectors in MM. The x2x_2 term is the error in the approximation.


Example: Let V=R2V=\mathbb{R}^2 and M=span{[1,1]T}M = \text{span}\{[1,1]^T\}. Find the best approximation of x=[4,7]Tx=[4,7]^T in MM.

Solution: We need to find mm^* such that m=α[11]m^* = \alpha \begin{bmatrix} 1 \\ 1 \end{bmatrix} and xm\|x-m^*\| is minimum.

(xm)M    <xm,m>=0mM(x-m^*) \perp M \implies <x-m^*, m> = 0 \quad \forall m \in M
<xm,[11]>=0<x-m^*, \begin{bmatrix} 1 \\ 1 \end{bmatrix}> = 0
Replace x and m with their values.\text{Replace $x$ and $m^*$ with their values.}
<[4α7α],[11]>=0<\begin{bmatrix} 4-\alpha \\ 7-\alpha \end{bmatrix}, \begin{bmatrix} 1 \\ 1 \end{bmatrix}> = 0
Recall that <x,y>=xTy.\text{Recall that $1lt;x,y> = x^Ty$.}
4α+7α=04-\alpha + 7-\alpha = 0
α=112\alpha = \frac{11}{2}
m=112[11]m^* = \frac{11}{2} \begin{bmatrix} 1 \\ 1 \end{bmatrix}

Example: Let xVx \in V and M=span{v1,v2}M = \text{span}\{v_1, v_2\}. Find the best approximation of xx in MM.

Solution: We need to find mm^* such that m=α1v1+α2v2m^* = \alpha_1 v_1 + \alpha_2 v_2 that is in the span of MM and xm\|x-m^*\| is minimum.

(xm)M    (xm)both v1 and v2(x-m^*) \perp M \implies (x-m^*) \perp \text{both } v_1 \text{ and }v_2
<xα1v1α2v2,v1>=<x,v1>α1<v1,v1>α2<v2,v1>=0<x-\alpha_1 v_1 - \alpha_2 v_2, v_1> = <x, v_1> - \alpha_1 <v_1, v_1> - \alpha_2 <v_2, v_1> = 0
<xα1v1α2v2,v2>=<x,v2>α1<v1,v2>α2<v2,v2>=0<x-\alpha_1 v_1 - \alpha_2 v_2, v_2> = <x, v_2> - \alpha_1 <v_1, v_2> - \alpha_2 <v_2, v_2> = 0
[<v1,v1><v2,v1><v1,v2><v2,v2>][α1α2]=[<x,v1><x,v2>]\begin{bmatrix} <v_1, v_1> & <v_2, v_1> \\ <v_1, v_2> & <v_2, v_2> \end{bmatrix} \begin{bmatrix} \alpha_1 \\ \alpha_2 \end{bmatrix} = \begin{bmatrix} <x, v_1> \\ <x, v_2> \end{bmatrix}
[α1α2]=[<v1,v1><v2,v1><v1,v2><v2,v2>]1[<x,v1><x,v2>]\begin{bmatrix} \alpha_1 \\ \alpha_2 \end{bmatrix} = \begin{bmatrix} <v_1, v_1> & <v_2, v_1> \\ <v_1, v_2> & <v_2, v_2> \end{bmatrix}^{-1} \begin{bmatrix} <x, v_1> \\ <x, v_2> \end{bmatrix}
m=α1v1+α2v2m^* = \alpha_1 v_1 + \alpha_2 v_2

Example: Let V=R3V = \mathbb{R}^3 and M=span{[1,1,1]T,[1,0,1]T}M = \text{span}\{[1,1,1]^T, [1,0,1]^T\}. Find the best approximation of x=[4,7,2]Tx=[4,7,2]^T in MM.

Solution: We need to find mm^* such that m=α1[111]+α2[101]m^* = \alpha_1 \begin{bmatrix} 1 \\ 1 \\ 1 \end{bmatrix} + \alpha_2 \begin{bmatrix} 1 \\ 0 \\ 1 \end{bmatrix} that is in the span of MM and xm\|x-m^*\| is minimum.

(xm)M    (xm)both v1 and v2(x-m^*) \perp M \implies (x-m^*) \perp \text{both } v_1 \text{ and }v_2
[<v1,v1><v2,v1><v1,v2><v2,v2>][α1α2]=[<x,v1><x,v2>]\begin{bmatrix} <v_1, v_1> & <v_2, v_1> \\ <v_1, v_2> & <v_2, v_2> \end{bmatrix} \begin{bmatrix} \alpha_1 \\ \alpha_2 \end{bmatrix} = \begin{bmatrix} <x, v_1> \\ <x, v_2> \end{bmatrix}
Recall that <x,y>=xTy.\text{Recall that $1lt;x,y> = x^Ty$.}
[3222][α1α2]=[136]\begin{bmatrix} 3 & 2 \\ 2 & 2 \end{bmatrix} \begin{bmatrix} \alpha_1 \\ \alpha_2 \end{bmatrix} = \begin{bmatrix} 13 \\ 6 \end{bmatrix}
[α1α2]=[3222]1[136]\begin{bmatrix} \alpha_1 \\ \alpha_2 \end{bmatrix} = \begin{bmatrix} 3 & 2 \\ 2 & 2 \end{bmatrix}^{-1} \begin{bmatrix} 13 \\ 6 \end{bmatrix}
[α1α2]=[1113/2][136]\begin{bmatrix} \alpha_1 \\ \alpha_2 \end{bmatrix} = \begin{bmatrix} 1 & -1 \\ -1 & 3/2 \end{bmatrix} \begin{bmatrix} 13 \\ 6 \end{bmatrix}
[α1α2]=[74]\begin{bmatrix} \alpha_1 \\ \alpha_2 \end{bmatrix} = \begin{bmatrix} 7 \\ -4 \end{bmatrix}
m=α1v1+α2v2=7[111]4[101]=[373]m^* = \alpha_1 v_1 + \alpha_2 v_2 = 7 \begin{bmatrix} 1 \\ 1 \\ 1 \end{bmatrix} - 4 \begin{bmatrix} 1 \\ 0 \\ 1 \end{bmatrix} = \begin{bmatrix} 3 \\ 7 \\ 3 \end{bmatrix}

Example: Let HH be the space of square integrable functions on [π,π][-\pi , \pi ] with inner product <f,g>=ππf(t)g(t)ˉdt<f,g> = \int_{-\pi}^{\pi} f(t)\bar{g(t)}dt. Let MM be the subspace of HH, M=span{ejkt/2π}M = \text{span}\{e^{jkt}/\sqrt{2\pi}\}, k from N to Nk \text{ from } -N \text{ to } N. Note that dimension of MM is 2N+12N+1.

<fn,fm>=ππejnt2πejmt2πdt=12πππej(nm)tdt<f_n, f_m> = \int_{-\pi}^{\pi} \frac{e^{jnt}}{\sqrt{2\pi}} \frac{e^{-jmt}}{\sqrt{2\pi}} dt = \frac{1}{2\pi} \int_{-\pi}^{\pi} e^{j(n-m)t} dt
If nm, then 12πππej(nm)tdt=12πej(nm)tj(nm)ππ=0\text{If $n \neq m$, then } \frac{1}{2\pi} \int_{-\pi}^{\pi} e^{j(n-m)t} dt = \frac{1}{2\pi} \frac{e^{j(n-m)t}}{j(n-m)} \Big|_{-\pi}^{\pi} = 0
If n=m, then 12πππej(nm)tdt=12πππ1dt=1\text{If $n = m$, then } \frac{1}{2\pi} \int_{-\pi}^{\pi} e^{j(n-m)t} dt = \frac{1}{2\pi} \int_{-\pi}^{\pi} 1 dt = 1
Therefore, <fn,fm>={1if n=m0if nm\text{Therefore, } <f_n, f_m> = \begin{cases} 1 & \text{if $n = m$} \\ 0 & \text{if $n \neq m$} \end{cases}

Now, let gHg \in H be an arbitrary function. Then g=g1+g2g = g_1 + g_2 where g1Mg_1 \in M and g2Mg_2 \in M^{\perp}. We need to find g1g_1 such that gg1\|g-g_1\| is minimum.

g1=k=NNαkejkt2π where αk=<g,fk>=ππg(t)ejkt2πdt g_1 = \sum_{k=-N}^{N} \alpha_k \frac{e^{jkt}}{\sqrt{2\pi}} \text{ where } \alpha_k = <g, f_k> = \int_{-\pi}^{\pi} g(t) \frac{e^{-jkt}}{\sqrt{2\pi}} dt
αk=ππg(t)ejkt2πdt \alpha_k = \int_{-\pi}^{\pi} g(t) \frac{e^{-jkt}}{\sqrt{2\pi}} dt
g1=k=NNππg(t)ejkt2πejkt2πdt=k=NNππg(t)12πdt=ππg(t)dt g_1 = \sum_{k=-N}^{N} \int_{-\pi}^{\pi} g(t) \frac{e^{-jkt}}{\sqrt{2\pi}} \frac{e^{jkt}}{\sqrt{2\pi}} dt = \sum_{k=-N}^{N} \int_{-\pi}^{\pi} g(t) \frac{1}{2\pi} dt = \int_{-\pi}^{\pi} g(t) dt

Example: Find the orthagonal projection of the vector [100]\begin{bmatrix} 1 \\ 0 \\ 0 \end{bmatrix} onto the subspace M=span{[111],[111]}M = \text{span}\{\begin{bmatrix} 1 \\ 1 \\ 1 \end{bmatrix}, \begin{bmatrix} 1 \\ -1 \\ 1 \end{bmatrix}\}.

Solution: We know that the projection matrix is P=B(BTB)1BTP = B(B^TB)^{-1}B^T where BB is the matrix whose columns are the basis vectors of MM. Therefore,

B=[111111]B = \begin{bmatrix} 1 & 1 \\ 1 & -1 \\ 1 & 1 \end{bmatrix}
BTB=[3113]B^TB = \begin{bmatrix} 3 & 1 \\ 1 & 3 \end{bmatrix}
P=[111111][3113]1[111111]P = \begin{bmatrix} 1 & 1 \\ 1 & -1 \\ 1 & 1 \end{bmatrix} \begin{bmatrix} 3 & 1 \\ 1 & 3 \end{bmatrix}^{-1} \begin{bmatrix} 1 & 1 & 1 \\ 1 & -1 & 1 \end{bmatrix}
P=[111111][3/81/81/83/8][111111]P = \begin{bmatrix} 1 & 1 \\ 1 & -1 \\ 1 & 1 \end{bmatrix} \begin{bmatrix} 3/8 & -1/8 \\ -1/8 & 3/8 \end{bmatrix} \begin{bmatrix} 1 & 1 & 1 \\ 1 & -1 & 1 \end{bmatrix}
P=[1/201/20101/201/2]P = \begin{bmatrix} 1/2 & 0 & 1/2 \\ 0 & 1 & 0 \\ 1/2 & 0 & 1/2 \end{bmatrix}
P[100]=[1/201/2]P \begin{bmatrix} 1 \\ 0 \\ 0 \end{bmatrix} = \begin{bmatrix} 1/2 \\ 0 \\ 1/2 \end{bmatrix}

#EE501 - Linear Systems Theory at METU